package array

func combinationSum2(candidates []int, target int) [][]int {
	res := [][]int{}

	var backtrack func(target int, sum int, track []int, candidates []int)
	backtrack = func(target, sum int, track, candidates []int) {
		if target == sum {
			temp := make([]int, len(track))
			copy(temp, track)
			res = append(res, temp)
			return
		} else if sum > target {
			return
		}

		for i, v := range candidates {

			track = append(track, v)
			backtrack(target, sum+v, track, candidates[i+1:])
			track = track[:len(track)-1]
		}
	}

	backtrack(target, 0, []int{}, candidates)
	return res
}
